open Graphics;;

if Array.length Sys.argv <> 3 then
  (print_string "error : 2 args size and speed\n";
   exit 2);;


let size = int_of_string Sys.argv.(1);;

let zoom = int_of_float (900. /. (float_of_int size));;

let delay_time = 0.01 /. (float_of_string Sys.argv.(2));;

type door = Left | Right | Top | Bottom;;
type cell ={ mutable color: int;
	     mutable doors: door list;
	   };;

type labyrinth ={ width: int;
		  height: int;
		  cells: cell array array;
		};;

Random.init (int_of_float (Sys.time () *.1000.));;

let new_labyrinth w h=
  let mat= Array.make_matrix h w {color=0; doors=[]}in
    for i=0 to h-1 do
      for j=0 to w-1 do 
	mat.(i).(j)<-{color=i*w+j; doors=[]};
      done;
    done;
{width=w;height=h;cells=mat};;

let open_door lab x y door =
  lab.cells.(y).(x).doors <- door::lab.cells.(y).(x).doors;;

let door_opened lab x y door = 
  List.exists ((=) door) lab.cells.(y).(x).doors;;

let door_closed lab x y door =
  not(door_opened lab x y door);;

let neighboor x y door =
  match door with
    | Left -> (x-1,y)
    | Right -> (x+1,y)
    | Top -> (x,y-1)
    | Bottom -> (x,y+1)
;;

let opposite door =
  match door with
    | Left -> Right
    | Right -> Left
    | Top -> Bottom
    | Bottom -> Top
;;

let rm_door dlist (d:door) = 
  List.filter ((<>) d) dlist;; 

let all_doors = [Left; Right; Top; Bottom];;

let rec choose_door laby op = 
  let y = Random.int laby.width in
  let x = Random.int laby.height in
  let d = List.nth all_doors (Random.int (List.length all_doors)) in
  let f x = () in 
  let (xn,yn) = neighboor x y d in
  try 
    f laby.cells.(yn).(xn);
    op laby x y d
  with Invalid_argument "index out of bounds" ->
    choose_door laby op
;;

let change_color laby x y c =
  laby.cells.(y).(x).color <- c
;;

let rec propage_color lab x y dlist c =
  match dlist with 
    | [] -> change_color lab x y c
    | e::r -> let (xn,yn) = (neighboor x y e) in 
	change_color lab x y c;
	propage_color lab xn yn (rm_door lab.cells.(yn).(xn).doors (opposite e)) c;
	propage_color lab x y r c
;;


let connect laby x y d =
  let (xn,yn) = (neighboor x y d) in
  let prim_color = laby.cells.(y).(x).color in
    if (door_closed laby x y d) && 
      (door_closed laby xn yn (opposite d)) &&
      (laby.cells.(yn).(xn).color <> prim_color) then
	(propage_color laby xn yn laby.cells.(yn).(xn).doors prim_color;
	 open_door laby x y d;
	 open_door laby xn yn (opposite d));
;;

let arret laby = 
  let res = ref true in
  let color0 = laby.cells.(0).(0).color in
    for i=0 to laby.width - 1 do
      for j=0 to laby.height - 1 do
	if laby.cells.(i).(j).color <> color0 then
	  res := false
      done;
    done;
    !res;;

let make_labyrinth width height =
  let laby = new_labyrinth width height in
    while not(arret laby) do
      choose_door laby connect 
    done;
    laby
;;

let draw_cell laby x y =
  let test_door = door_closed laby x y in
  let new_y = (laby.height - y - 1)*zoom in
  let new_x = x*zoom in
    if test_door Top then
      (moveto new_x (new_y+zoom);
       lineto (new_x+zoom) (new_y+zoom));
    if test_door Bottom then
      (moveto new_x new_y;
       lineto (new_x+zoom) new_y);
    if test_door Left then
      (moveto new_x new_y;
       lineto new_x (new_y+zoom));
    if test_door Right then
      (moveto (new_x+zoom) new_y;
       lineto (new_x+zoom) (new_y+zoom))
    
;;

let color_cell laby x y color =
  set_color color;
  let margin = zoom / 8 in
  fill_rect 
    ((x*zoom)+margin) 
    (((laby.height-y-1)*zoom)+margin) 
    (zoom-2*margin) 
    (zoom-2*margin)
;;

let rec fill_laby lab x y dlist c =
  set_color c;
  match dlist with 
    | [] -> color_cell lab x y c
    | e::r -> 
	let (xn,yn) = (neighboor x y e) in 
	let ndoors = rm_door lab.cells.(yn).(xn).doors (opposite e) in
	  color_cell lab x y c;
	  fill_laby lab xn yn ndoors c;
	  fill_laby lab x y r c
;;
  
let windows_size laby = 
  open_graph (Printf.sprintf " %dx%d" 
		(laby.width*zoom) 
		(laby.height*zoom)
	     )
;;

let continue () =
  let ev = wait_next_event [Key_pressed] in
    ev.key <> 'q'
;;

let show_labyrinth laby =
  windows_size laby;
  for i=0 to laby.height-1 do
    for j=0 to laby.width-1 do
      draw_cell laby j i
    done;
  done;
  
  try 
    while continue () do
      ()
    done;
  with Graphics.Graphic_failure("fatal I/O error") ->
    close_graph ()
;;

exception CellFound;;

let rec explore laby x y doors ex ey =
  (try Thread.delay delay_time with _ -> ());
  if ex=x && ey=y then 
    (color_cell laby x y black;
     raise CellFound)
  else
      match doors with
	  
	| [] -> true
	| e::[] -> 
	    let (xn,yn) = (neighboor x y e) in
	    let ndoors = rm_door laby.cells.(yn).(xn).doors (opposite e) in
	      color_cell laby x y black;
	      explore laby xn yn ndoors ex ey
	| e::r -> 
	    let (xn,yn) = (neighboor x y e) in
	    let ndoors = rm_door laby.cells.(yn).(xn).doors (opposite e) in
	      color_cell laby x y black;
	      if explore laby xn yn ndoors ex ey then
		(fill_laby laby xn yn ndoors (rgb 204 0 0);
		 explore laby x y r ex ey)
	      else
		false
;;

let solve laby x y ex ey =
  try 
    explore laby x y laby.cells.(y).(x).doors ex ey
  with CellFound ->
    true
;;

let solve_labyrinth laby =
  windows_size laby;

  for i=0 to laby.height-1 do
    for j=0 to laby.width-1 do
      draw_cell laby j i
    done;
  done;
  
  
  if solve laby 0 0 (laby.width-1) (laby.height-1) then
  try 
    while continue () do
      ()
    done;
  with Graphics.Graphic_failure("fatal I/O error") ->
    close_graph(); exit 0
    
;;

solve_labyrinth (make_labyrinth size size);;
